382B - Number Busters - CodeForces Solution

#include <iostream>
#include <cassert>
#include <map>

using namespace std;


long long a, b, w, x, c, res;

bool sim_once(long long& t1, long long& t2){

    while(b < x) b += w, a --, c --, res ++, t1 ++;
    assert(b >= x);

    while(b >= x){
        b -= x, c --, res ++, t2 ++;
        if(c <= a){
            cout << res << '\n';
            return true;
        }
    }
    assert(b < x);
    return false;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> w >> x >> c;
    if(c <= a){
        cout << 0 << '\n';
        return 0;
    }

    res = 0;
    w -= x;

    map<int, pair<long long, long long>> start_set;
    long long pre_t1 = 0, pre_t2 = 0;
    start_set[b] = {pre_t1, pre_t2};
    long long t1, t2;
    while(true){
//        int start_b = b;
        if(sim_once(pre_t1, pre_t2)) return 0;

        if(start_set.count(b)){
            t1 = pre_t1 - start_set[b].first;
            t2 = pre_t2 - start_set[b].second;
            break;
        }
        else start_set[b] = {pre_t1, pre_t2};
    }

    long long k = (c - a) / t2 + !!((c - a) % t2);
    assert(k >= 1);
    k --;
    res += k * (t1 + t2);
    a -= k * t1, c -= k * (t1 + t2);

//    cout << res << '\n';
//    cout << c << ' ' << a << ' ' << t1 << ' ' << t2 << '\n';
    if(c <= a) cout << res << '\n';
    else{
        assert(c - a <= t2);
        while(!sim_once(t1, t2));
    }

    return 0;
}